已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,A*N−1的中位数指*A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。

输入格式：

输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

输出格式：

在一行中输出两个输入序列的并集序列的中位数。

输入样例1：

1
2
3
5
1 3 5 7 9
2 3 4 5 6

输出样例1：

1
4

输入样例2：

1
2
3
6
-100 -10 1 1 1 1
-50 0 2 3 4 5

输出样例2：

1
1

思路

最直接的方法就是将给定的2*n个数存入数组中，对数组排序，排序复杂度为O(nlogn)

但是这样就没有利用题目所说的两个给定数组均有序的特点

我们可以将两个有序数组合并成一个仍然有序数组，然后取中间的值即可，合并两有序数组方法为：

  • 不断取出两数组中较小的数存入新数组，直到两数组为空（具体看代码）

这样时间复杂度可以是O(n)，相当于遍历一遍两个数组

知识点：两有序数组的合并

代码

如下为合并方法，时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> ve1, ve2;
    for(int i = 1; i <= n; i++) {//输入数组
        int id;
        cin >> id;
        ve1.push_back(id);
    }
    for(int i = 1; i <= n; i++) {//输入数组
        int id;
        cin >> id;
        ve2.push_back(id);
    }
    int a = 0, b = 0; //分别代表两数组当前最小数的位置
    vector<int> ret;//存储合并结果，其实可以把结果放到ve1中
    while(a < n && b < n) {
        //取出较小的
        if(ve1[a] < ve2[b]) {
            ret.push_back(ve1[a]);
            a++;
        } else {
            ret.push_back(ve2[b]);
            b++;
        }
    }
    while(a < n) {//取出ve1中剩余的
        ret.push_back(ve1[a]);
        a++;
    }
    while(b < n) {//取出ve2中剩余的
        ret.push_back(ve2[b]);
        b++;
    }
    cout << ret[(ret.size() - 1) / 2] << endl;//或者ret[(2*n-1)/2]
    return 0;
}

如下为排序方法，时间复杂度O(nlogn)，也可通过，不会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> ve;
    for(int i = 1; i <= n; i++) {
        int id;
        cin >> id;
        ve.push_back(id);
    }
    for(int i = 1; i <= n; i++) {
        int id;
        cin >> id;
        ve.push_back(id);
    }
    sort(ve.begin(), ve.end());
    cout << ve[(2 * n - 1) / 2] << endl;
    return 0;
}